package com.fps.webshop.question.question0700_0799;

import com.fps.webshop.question.common.TreeNode;

/**
 * 701. 二叉搜索树中的插入操作
 * 
 * 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
 * 
 * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
 * 
 * 示例 1：
 * 输入：root = [4,2,7,1,3], val = 5
 * Question701_01.jpg
 * 输出：[4,2,7,1,3,5]
 * Question701_02.jpg
 * 解释：另一个满足题目要求可以通过的树是：Question701_03.jpg
 * 
 * 示例 2：
 * 输入：root = [40,20,60,10,30,50,70], val = 25
 * 输出：[40,20,60,10,30,50,70,null,null,25]
 * 
 * 示例 3：
 * 输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
 * 输出：[4,2,7,1,3,5]
 * 
 * 提示：
 * 		给定的树上的节点数介于 0 和 10^4 之间
 * 		每个节点都有一个唯一整数值，取值范围从 0 到 10^8
 * 		-10^8 <= val <= 10^8
 * 		新值和原始二叉搜索树中的任意节点值都不同
 */
public class Question701 {
	
	/**
	 * 第一次提交，二叉树迭代，把数据全部插在叶子节点上
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.1 MB	Java	2021/08/24 11:25
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.1 MB, 在所有 Java 提交中击败了52.75%的用户
	 */
	public static TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) {
        	return new TreeNode(val);
        }
        TreeNode roottmp = root;
    	while(true) {
    		if(root.val>val) {
        		if(root.left==null) {
            		root.left = new TreeNode(val);
            		return roottmp;
        		}
        		root = root.left;
    		}else {
    			if(root.right==null) {
            		root.right = new TreeNode(val);
            		return roottmp;
        		}
    			root = root.right;
    		}
    	}
    }
	
	

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		TreeNode leftNode1 = new TreeNode(2);
		//TreeNode rightNode1 = new TreeNode(-57);
		root.left = leftNode1;
		//root.right = rightNode1;
		
		//TreeNode rightNode2 = new TreeNode(67);
		//leftNode1.right = rightNode2;
		
		//TreeNode leftNode3 = new TreeNode(67);
		//rightNode1.left = leftNode3;
		
		System.out.print(insertIntoBST(root,1));
		
	}
}
